package slidingWindowMaximum_239;

import java.util.Arrays;
import java.util.LinkedList;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        int left = 0, right = 0;
        LinkedList<Integer> list = new LinkedList<>();
        while (right < nums.length) {
            while (!list.isEmpty() && list.getLast() < nums[right]) {
                list.removeLast();
            }
            list.addLast(nums[right]);
            if (right - left + 1 == k) {
                result[left] = list.getFirst();
                if (nums[left++] == list.getFirst()) {
                    list.removeFirst();
                }
            }
            right++;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
}
